ence alignment

NA or RNA or protein sequence analysis is one important area in

biology. There are several separate subjects in the area of

analysis. Two subjects are the fundamental stones for the modern

They are the sequence homology alignment problem [Lipman,

89; Thompson and Plewniak, 1999; Nguyen, et al., 216] and the

assembly problem [Myers, et al., 2000]. The former compares

ore than two sequences to discover how sequences are similar to

er so that the annotation of a novel sequence can be made. The

ults from the modern sequencing technology, where a sequencing

nt will generate millions of short sequencing segments which are

quencing reads for a genome. It is required to assemble these

ng reads to generate longer sequencing segments before being

r mapped to a reference genome for further study.

equence homology alignment is used to determine how similar

ences are. This approach has at least three benefits. First, species

ary history can be revealed through an alignment of the collected

s for a species or an organism [Voronova and Chelomina, 2020].

also be extended to cross-species and cross-organisms studies

et al., 2020]. Second, the sequence homology alignment approach

reveal some conserved segments which correspond to some

t genes in relation with biological properties of a species or an

, or in relation with some diseases [Caldovic, et al., 2014]. Third,

nce homology alignment approach can be used to reveal genetic

u, et al., 2019].

mining how similar two sequences are needs to determine the

tion for each character of each sequence and to quantitatively

e similarity between two sequences. Suppose there are two

s, x=CCGAATG and y=CCAATT. One alignment between these

ences is shown below,